package fun.pengzh.gui.demo;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author fun.pengzh
 * @class fun.pengzh.gui.demo.AStarSearch
 * @desc
 * @since 2022-02-01
 */
public class AStarSearch {

    public static ArrayList<int[]> AStarSearching(int[][] a, int x, int length, int width, int[] start, int[] end) {
        Queue<HListNode> queue = new PriorityQueue<>();
        boolean[][] visited = new boolean[length + 1][length + 1];
        ArrayList<int[]> list = new ArrayList<>(); // 储存路径
        for (int i = 0; i < a.length; i++) visited[a[i][0]][a[i][1]] = true;
        HListNode node_3 = new HListNode(start[0], start[1], 0, null, end);
        queue.add(node_3);
        visited[start[0]][start[1]] = true;
        HListNode node_2 = null; //捕获最终节点
        while (!queue.isEmpty()) {
            HListNode node = queue.poll();
            if (node.data[0] == end[0] && node.data[1] == end[1]) {
                node_2 = node;
                break;
            }
            if (node.data[0] + 1 < 31 && !visited[node.data[0] + 1][node.data[1]]) {
                HListNode node_1 = new HListNode(node.data[0] + 1, node.data[1], node.n + 1, node, end);
                queue.add(node_1);
                visited[node.data[0] + 1][node.data[1]] = true;
            }
            if (node.data[0] - 1 > -1 && !visited[node.data[0] - 1][node.data[1]]) {
                HListNode node_1 = new HListNode(node.data[0] - 1, node.data[1], node.n + 1, node, end);
                queue.add(node_1);
                visited[node.data[0] - 1][node.data[1]] = true;
            }
            if (node.data[1] + 1 < 31 && !visited[node.data[0]][node.data[1] + 1]) {
                HListNode node_1 = new HListNode(node.data[0], node.data[1] + 1, node.n + 1, node, end);
                queue.add(node_1);
                visited[node.data[0]][node.data[1] + 1] = true;
            }
            if (node.data[1] - 1 > -1 && !visited[node.data[0]][node.data[1] - 1]) {
                HListNode node_1 = new HListNode(node.data[0], node.data[1] - 1, node.n + 1, node, end);
                queue.add(node_1);
                visited[node.data[0]][node.data[1] - 1] = true;
            }
        }
        if (node_2 == null) return new ArrayList<>();
        while (node_2 != null) {
            int[] data = new int[2];
            data[0] = node_2.data[0];
            data[1] = node_2.data[1];
            list.add(data);
            node_2 = node_2.parent;
        }
        return list;
    }

}

class HListNode implements Comparable<HListNode> {
    int[] data = new int[2];
    HListNode parent;
    int n;
    int[] end;

    public HListNode(int x, int y, int n, HListNode list, int[] end) {
        this.data[0] = x;
        this.data[1] = y;
        this.n = n;
        this.end = end;
        this.parent = list;
    }

    public HListNode() {

    }

    public int compareTo(HListNode node) {
        int a1 = this.n + Math.abs(this.data[0] - end[0]) + Math.abs(this.data[1] - end[1]);
        int a2 = (node.n + Math.abs(node.data[0] - end[0]) + Math.abs(node.data[1] - end[1]));
        return (a1 < a2) ? -1 : 1;
    }
}
